package j2024.j202408;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class j0804 {


    List<List<String>> ret;
    char[][] path;
    boolean[] col;
    boolean[] dig1;
    boolean[] dig2;
    int nmax = 0;

    /**
     * 51. N 皇后
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        ret =  new ArrayList<>();
        path = new char[n][n];
        col = new boolean[n];
        dig1 = new boolean[2*n];
        dig2 = new boolean[2*n];
       nmax = n;
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i],'.');
        }
       dfs(0);
        return ret;
    }
    public void dfs(int pos){
        if(pos==nmax){
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < nmax; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
        }
        for (int i = 0; i < nmax; i++) {
            if(col[i]==false && dig1[pos-i+nmax]==false && dig2[pos+i]==false){
                path[pos][i] = 'Q';
                col[i] = true;
                dig1[pos-i+nmax]=true;
                dig2[pos+i]=true;
                dfs(pos+1);
                col[i] = false;
                dig1[pos-i+nmax]=false;
                dig2[pos+i]=false;
                path[pos][i] = '.';
            }
        }
    }


}
class pro{
    boolean[][] row;
    boolean[][] col;
    boolean[][][] grid;

    /**
     * 36. 有效的数独
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]!='.'){
                    int pos = board[i][j]-'0';
                    if(row[i][pos] || col[j][pos] || grid[i/3][j/3][pos]){
                        return false;
                    }
                    row[i][pos] = col[j][pos]= grid[i/3][j/3][pos]=true;
                }
            }
        }
        return true;
    }
}
class shudu{
    /**
     * 37. 解数独
     */
    boolean[][] row;
    boolean[][] col;
    boolean[][][] grid;
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]!='.'){
                    int tmp = board[i][j]-'0';
                    row[i][tmp] = col[j][tmp] = grid[i/3][j/3][tmp] = true;
                }
            }
        }
        dfs(board);
    }

    public boolean dfs(char[][] board){
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]=='.'){
                    for (int k = 1; k <= 9; k++) {
                        if(row[i][k]==false && col[j][k]==false && grid[i/3][j/3][k]==false){
                            board[i][j] = (char)(k+'0');
                            row[i][k] = col[j][k] = grid[i/3][j/3][k] = true;
                            if(dfs(board)==true){
                                return  true;
                            }
                            board[i][j] = '.';
                            row[i][k] = col[j][k] = grid[i/3][j/3][k] = false;
                        }
                    }
                    return false;
                }
            }
        }
        return  true;
    }
}
class words{
    /**
     * 79. 单词搜索
     */
    boolean[][] vis;
    int[] dx  = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    char[] words;
    public boolean exist(char[][] board, String word) {
        words = word.toCharArray();
        int n = board.length,m = board[0].length;
        vis = new boolean[n][m];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]==words[0]){
                    vis[i][j] = true;
                    if(dfs(board,i,j,1)){
                        return true;
                    }
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i,int j,int wi){
        if(wi==words.length){
            return true;
        }
        for (int k = 0; k < 4; k++) {
            int x = i+dx[k];
            int y = j+dy[k];
            if(x>=0 & x<board.length && y>=0 && y<board[0].length && vis[x][y]==false && board[x][y]==words[wi]){
                vis[x][y] = true;
                if(dfs(board,x,y,wi+1)){
                    return true;
                }
                vis[x][y] = false;
            }
        }
        return false;
    }
}
